1. Field of the Invention
The present invention relates to a concurrency control method and related system for use with database management systems and, more particularly, to such a concurrency control that is used to ensure the correct execution of multiple concurrent global transactions in a heterogeneous distributed database system in the presence of local transactions that are outside of the control of this system.
2. Setting of the Invention
A multidatabase system (MDBS) provides uniform user query access to one or more heterogeneous database management systems that may be located at different sites or at one site. In using an MDBS, a user is not required to know the location or the characteristics of the data needed for the transaction. Also, the MDBS query and data access language allows the user to access multiple preexisting databases in a single query using a predefined global query language. Therefore, the knowledge of the intriacacies of each of the local database management systems supporting the data is not required. This universality of access to databases is a feature of Amoco Production Company's Distributed Database System (ADDS), as described in "ADDS--Heterogeneous Distributed Database System," by Y. J. Breitbart and L. R. Tieman, Distributed Data Sharing Systems, North-Holland Publ., 1985.
It is preferable in using an MDBS that no modification of the local database management systems is required or permitted so that the autonomy of the local databases is preserved and applications that are locally written still are able to run even in the presence of the MDBS. Modifying the DBMS's to interact with the MDBS could hinder the developers of the MDBS when support for a new DBMS is added. Also, changes to the DBMS software are oftentimes not permitted under certain vendor supplied software license agreements and, more importantly, these changes can create problems with the maintenance of user applications as well as with the maintenance of the DBMS software.
Since changes to the local database software are not permitted, the DBMS's should treat the global subtransactions and local transactions equally and, in addition, the local DBMS's should be able to coordinate their operations without knowledge of other DBMS's involved and without knowledge of the MDBS. Local autonomy also requires that local DBMS maintenance and performance changes be allowed to continue as if the MDBS does not exist.
In general, a DBMS may utilize one of a variety of different data models such as hierarchical, relational, network. A variety of different local area and wide area communication networks can be used to communicate with the DBMS's. The MDBS must be able to support access to the DBMS regardless of the data model and communications facilities utilized.
The absence of cooperative action among the local DBMS's creates several difficult problems in maintaining database consistency of semantically related data located at different data sites and managed by different DBMS.varies.s. Among these problems are maintaining global database consistency in the absence of information about transactions executing at other local sites, preventing and/or detecting deadlock situations in the execution of global and local transactions, generating and executing subtransactions based on global transactions submitted to the MDBS, maintaining global transaction and subtransaction atomicity, preserving the relative execution order of the transactions, as determined by the MDBS, at local sites.
In a multidatabase system where only global transactions are permitted, homogeneous distributed database management system concurrency control techniques can be employed. However, from a practical standpoint, this restriction significantly diminishes the usefulness of the system, i.e., only global transactions are permitted. It is preferable for the users of the system to be allowed to submit transactions outside of the control of the MDBS. However, permitting the execution of some types of local transactions may create semantic inconsistencies in the global database.
An example of a local transaction that creates a semantic inconsistency is described herein. For a multidatabase system that supports access to data located at sites A and B, site A supports access to data items x and y and site B supports access to data items x and z. Assuming that x is a replicated data item in the global database and initially the value of x is the same at both sites, if a local transaction is submitted at site A and changes the value of x, then the global database is no longer consistent because the value of x is not the same at both sites. Therefore, it is clear that the execution of some types of local transactions in a multidatabase environment should be prohibited. The inventors hereof know of no other system or method for permitting the correct execution of multiple concurrent transactions, each containing one or more read and/or write operations, in a heterogeneous database system.
Various forms of concurrency controls have been developed for database management systems, including one described in the article "Architecture of the Network Data Management System" by Staniszkis, et al. In the Network Data Management System (NDMS), Staniszkis discusses updating heterogeneous databases, however, there is no disclosure or suggestion within Staniszkis for concurrency control to permit the correct execution of multiple concurrent transactions.
Another system described in "Sirius Systems for Distributed Database Management" by Litwin, et al., and "Heterogeneity in the Distributed Database Management Systems Sirius-Delta" by Ferrier, et al., discloses updating data within distributed databases. However, the Sirius-Delta system must modify each local DBMS and use a prior concurrency control. There is no disclosure or suggestion for the Sirius-Delta system to not require altering each of the local database management systems, or for permitting the correct execution of multiple concurrent transaction in a heterogeneous database system, including independent execution of local transactions at each site.
U.S. Pat. No. 4,627,019 discloses a concurrency control that only works with a local relational database management system. There is no disclosure or suggestion within U.S. Pat. No. 4,627,019 of a concurrency control to be used with a heterogeneous distributed database system, further, that can be used with any nonrelational database management system if the user so desires.
There is a need for a concurrency control method and system for permitting the correct execution of multiple concurrent transactions in a heterogeneous database system without any modifications to the local database management systems, and which can be used with any desired database management system.